package immutablecollections;

import immutablecollections.exceptions.*;
import immutablecollections.functions.*;
import java.util.*;
/**
 * A zipper on an {@link ImList} lets you navigate back and forth in the list and "mutate" it as you go.
 * 
 * ### Introduction
 * 
 * `ImListZipper` is to `Imlist` what `java.util.ListIterator` is to `java.util.List`. It is a cursor that lets you
 * navigate back and forward within a list and to add/replace/delete elements relative to the current position.
 * 
 * Of course, since `Im` collections
 * are immutable, you cannot *actually* mutate the underlying list.
 * Instead, methods that "mutate" the zipper return new zippers.
 * For example {@link #next()} returns a *new* zipper pointing to the next element in the list
 * leaving the original zipper unchanged. After "mutating" the zipper, you have to use {@link #close()}
 * which returns the new list with the changes made to it.
 * 
 * ### next() and prev() and the "pair of lists" analogy
 * 
 * A good way to think of a list zipper is as a pair of lists formed out of the original list.
 * The *focus* element is the last element of the first list (if there is one).
 * 
 * If we consider the list `[1, 2, 3]`, when we get a zipper on it we get: 
 * 
 *     [] [1, 2, 3]
 * 
 * The first list is empty and the second list is just the original list. In this state, there is no focus element.
 * 
 * If we use `next()` we get a new zipper:
 * 
 *     [1] [2, 3]
 *     
 * The focus element on this zipper is `1`.
 * 
 * If we use `next()` on this new zipper we get this:
 * 
 *     [1, 2] [3]
 *     
 * The focus element on this zipper is `2`.
 * 
 * If we use `next()` on this new zipper we get this:
 * 
 *     [1, 2, 3] []
 *     
 * The focus element on this zipper is `3`.
 * 
 * If we use `prev()` on this, we get:
 * 
 *      [1, 2] [3]
 *      
 * So you can think of `next()` as moving the first element of the second list to the end of the first
 * list. `prev()` moves the last element of the first list to the start of the second list.
 * 
 * In fact the current implementation stores the lists as `ImLists` with the first list reversed so `next()` and
 * `prev()` are **`O`**`(1)` operations.
 * 
 * To "mutate" the zipper you can only operate on the focus - the last element of the first list. You can remove/replace it
 * and add elements after it.
 * 
 * The {@link #close()} method just joins the two lists together. It is **`O`**`(n)` where `n` is the size of the list.
 * 
 * {@link #getIndex()} returns the size of the first list.
 * 
 * ### The initial zipper state
 * 
 * As we stated above, when you get a zipper on a list, it will initially be in "before the start of the list" state
 * Let's call this the *initial state*.
 *
 * If
 * 
 *     z.getIndex() <= 1
 *     
 * then
 * 
 *     z.prev().prev() = z.prev()
 *
 * This means that, for zippers on non-empty lists, this is always true:
 * 
 *     z.prev().next() == z.getElement()
 *      
 * The ability to move to the initial state means that to insert an element before the focus,
 * you can use this:
 * 
 *     z.prev().push(x)
 *     
 * and it will work on any zipper on any position on a list of any size.
 *
 * When a zipper is in the initial state, three methods will throw {@link NoSuchElementException}:
 * 
 * * {@link #getFocus()}
 * * {@link #setFocus(Object)}
 * * {@link #pop()}
 * 
 * A zipper on the empty list looks like this:
 * 
 *     [] []
 * 
 * It be in the initial state. Additionally {@link #hasNext()} will be `false` and {@link #next()}
 * will throw {@link NoSuchElementException}.
 *
 *     
 * ### Inserting and removing elements
 * 
 * To insert an element, use `push()`. To remove the focus element use `pop()`:
 * 
 * push on this:
 * 
 *     [1, 2, 3] [8]
 * 
 * gives:
 * 
 *     [1, 2, 3, 5] [8]
 * 
 * and pop on this zipper will give:
 *     
 *     [1, 2, 3] [8]
 *     
 * The methods are so called because, if you imagine the first list as a stack with the focus element at the top
 * of the stack then you can think of
 * `push()` and `pop()` operating on this stack and they work as you would expect. 
 * 
 *  If the focus was the first element, the zipper returned by pop()
 *  will be in the initial state.
 *  
 *      [1] [2, 3] pop()  =>  [] [2, 3]
 *  
 *  This means that, for non-empty zipper `z` and any object `e`, pop() and push() are inverse operations:
 *  
 *     z.push(e).pop() 
 *     z.pop().push(z.getElement())
 *      
 * and code like this (for example):
 *  
 *      pop().insertAllAfter(newList)
 * 
 * will replace the focus with `newList` for any zipper on any position on any non-empty list.
 * 
 * For empty lists, you can't pop() - but push(e) followed by pop() will return a zipper on the empty list.
 * 
 * `push()` and `pop()` are **`O`**`(1)` operations.
 * 
 * ### Changing the focus
 * 
 * You can set the focus using setFocus()
 * 
 *     [1, 2] [3]   setfocus(5)  =>  [1, 5] [3]
 *     [1, 2, 3] [] setfocus(5)  =>  [1, 2, 5] []
 *     [] [...]     setfocus(5)  =>  throws ZipperHasNoFocusException
 * 
 * 
 * ### Using while loops or foreach
 * 
 * When you get a zipper on a list, it will initially be "before the start of the list". In order to get the first
 * element you have to use {@link #next()}. This is similar to `java.util.ListIterator` and allows you to write code like this:
 * 
 *     ImListZipper<Integer> z = ImList.onArray(1, 2, 3).getZipper();
 *  
 *     while (z.hasNext())
 *     {
 *         z = z.next();
 *         System.err.println(z.pop().close());
 *     }
 * 
 * which will display:
 * 
 *     [2, 3]
 *     [1, 3]
 *     [1, 2]
 *     
 * 
 * Zippers are also `iterable`. This code:
 * 
 *     for (ImListZipper<Integer> z : ImList.onArray(1, 2, 3).getZipper())
 *     {
 *         System.err.println(z.pop().close());
 *     }
 * 
 * will display the same output as the while loop example above.
 * 
 * The iterator will work on each element of the original list so, if you need to "mutate" it as you go then the
 * while loop is more useful. Here is an example that removes all elements except the first and last from a list.
 * 
 *     ImListZipper<Integer> z = ImList.onArray(1, 2, 3, 5).getZipper();
 * 
 *     while (z.hasNext())
 *     {
 *         z = z.next();
 *         if (z.hasPrev() && z.hasNext())
 *             z = z.pop();
 *     }
 * 
 *     z.close()  =>  [1, 5]
 * 
 * ### Example - permutations of a list
 * 
 * To generate the permutations of a list, one algorithm is to take each element `e` in turn from the list and cons
 * `e` with each list generated by the permutations of the list with element `e` removed. In pseudo-code:
 * 
 *     perms([1, 2, 3])  =  1 consed with all from perms([2, 3]) +
 *                          2 consed with all from perms([1, 3]) +
 *                          3 consed with all from perms([1, 2]) +
 * 
 * with
 * 
 *     perms([])  =  [[]]
 * 
 * Using a list zipper, this algorithm can be implemented fairly directly:
 * 
 *     public <T> ImList<ImList<T>> perms(ImList<T> list)
 *     {
 *         if (list.isEmpty())
 *             return ImList.on(ImList.<T> empty());
 *    
 *         ImList<ImList<T>> p = ImList.empty();
 *    
 *         for (ImListZipper<T> z : list.getZipper())
 *         {
 *             for (ImList<T> t : perms(z.pop().close()))
 *             {
 *                 p = p.cons(t.cons(z.getElement()));
 *             }
 *         }
 *    
 *         return p;
 *     }
 *     
 * For a more functional style, we could observe that consing an element `e` in turn with a list of lists, is the
 * same as mapping the function `f` over the list where:
 *  
 *      f(list) = list.cons(e)
 *      
 * If we are prepared to get the cons function directly we could write this:
 * 
 *     public <T> ImList<ImList<T>> perms2(ImList<T> list)   
 *     {
 *         if (list.isEmpty())
 *             return ImList.on(ImList.<T> empty());
 *    
 *         Function2<ImList<T>> consFn = FnFactory.on(ImList.class).getFnStatic( //
 *                 ImList.class, "cons", Object.class, ImList.class);
 *    
 *         ImList<ImList<T>> p = ImList.empty();
 *    
 *         for (ImListZipper<T> z : list.getZipper())
 *         {
 *             p = p.addingAll(perms2(z.pop().close()).map(consFn.invoke(z.getElement())));
 *         }
 *    
 *         return p;
 *     }
 *     
 * although here we saved one line of code but had to add another to do so.
 *   
 * If we wanted to have the cons function declared statically then we have a certain amount of ... finagling to do:
 * 
 *     static Function2<ImList<Object>> consFn1 = FnFactory.on(ImList.class).getFnStatic( //
 *             ImList.class, "cons", Object.class, ImList.class);
 * 
 *     [@]SuppressWarnings({ "unchecked" })
 *     private static <T> Function2<T> consFn()
 *     {
 *         return (Function2<T>) consFn1;
 *     }
 * 
 *     public <T> ImList<ImList<T>> perms3(ImList<T> list)
 *     {
 *         if (list.isEmpty())
 *             return ImList.on(ImList.<T> empty());
 * 
 *         ImList<ImList<T>> p = ImList.empty();
 * 
 *         for (ImListZipper<T> z : list.getZipper())
 *         {
 *             p = p.addingAll(perms3(z.pop().close()).map(ImListZipperTest.<ImList<T>> consFn().invoke(z.getElement())));
 *         }
 * 
 *         return p;
 *     }
 * 
 * ### Yet another permutations example
 * 
 * And finally (just when you thought this example had been done to death) there is another algorithm that can be
 * easily implemented using a list zipper.
 * 
 * In this algorithm
 * we take, the head `h`, of the list, calculates the permutions `p`, on the tail and then, for each list `l`, in `p`,
 * creates lists with `h` after each `n-th` element of `l` (where `n` goes from `0` to `l.size()`).
 * 
 * So, as an example, starting with:
 * 
 *     [1, 2, 3]
 * 
 * we calculate:
 * 
 *     perms([2, 3])  => [[2, 3], [3, 2]]
 *     
 * so we now need to insert the head `1` in every possible position in `[2, 3]` to form three lists:
 * 
 *     [1, 2, 3]  [2, 1, 3] [2, 3, 1]
 * 
 * and then do the same with `[3, 2]` to give another three:
 * 
 *     [1, 3, 2]  [3, 1, 2] [3, 2, 1]
 * 
 * Here is the code:
 * 
 *     public <T> ImList<ImList<T>> perms4(ImList<T> list)
 *     {
 *         if (list.isEmpty())
 *             return ImList.on(ImList.<T> empty());
 *     
 *         ImList<ImList<T>> p = ImList.empty();
 *     
 *         for (ImList<T> l : perms4(list.tail()))
 *         {
 *             p = p.cons(l.cons(list.head()));
 *  
 *             for (ImListZipper<T> z : l.getZipper())
 *                 p = p.cons(z.push(list.head()).close());
 *         }
 *     
 *         return p;
 *     }
 * 
 * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
 * for more details about zippers.
 *
 */
public class ImListZipper<T> implements Iterable<ImListZipper<T>>
{
    private final ImList<T> first;
    private final ImList<T> second;

    private ImListZipper(ImList<T> list)
    {
        this(ImList.<T> empty(), list);
    }

    private ImListZipper(ImList<T> before, ImList<T> after)
    {
        this.first = before;
        this.second = after;
    }

    static <TT> ImListZipper<TT> on(ImList<TT> list)
    {
        return new ImListZipper<TT>(list);
    }

    /**
     * The zipper whose focus is the next element in the list.
     * 
     * The first element of the second list is moved to the end of the first list:
     * 
     *     [1] [2, 3] next()  => [1, 2] [3]
     * 
     * @throws NoSuchElementException if no such element exists
     */
    public ImListZipper<T> next()
    {
        if (second.isEmpty())
        {
            if (first.isEmpty())
                throw new NoSuchElementException("The list is empty");
            else
                throw new NoSuchElementException("Already at the end of the list");
        }
        else
            return new ImListZipper<T>(first.cons(second.head()), second.tail());
    }

    /**
     * The zipper whose focus is the previous element in the first list (if there is one).
     * 
     * The last element of the first list (if there is one) is moved to the front of the second list:
     * 
     *     [1, 2] [3] prev()    => [1] [2, 3]
     *     [1] [2, 3] prev()    => [] [1, 2, 3]
     *     
     * If the first list is empty then `this` is returned.
     * 
     *     [] [1, 2, 3] prev()  => [] [1, 2, 3]
     * 
     * If the first list is now empty then you won't be able to set or get the focus or pop it.
     * 
     * Note that this means that you can always use `prev()` on a zipper - even if {@link #hasPrev()} is `false`
     */
    public ImListZipper<T> prev()
    {
        return first.isEmpty()
                ? this
                : new ImListZipper<T>(first.tail(), second.cons(first.head()));
    }

    /**
     * The list that the zipper represents, with all modifications made.
     * 
     * The lists are joined together:
     * 
     *     [1, 2] [3] close()  => [1, 2, 3]
     */
    public ImList<T> close()
    {
        if (first.isEmpty())
            return second;

        ImList<T> close = second;

        for (T a : first)
        {
            close = ImList.cons(a, close);
        }

        return close;
    }

    /**
     * The zipper that is the same as `this` except that the focus element is `newElement`.
     * 
     *     [1] [2, 3] setFocus(5)    => [5] [2, 3]
     *     [] [1, 2, 3] setFocus(5)  => throws ZipperHasNoFocusException
     *     
     * @throws ZipperHasNoFocusException if the first list is empty
     */
    public ImListZipper<T> setFocus(T newElement)
    {
        if (first.isEmpty())
            throw new ZipperHasNoFocusException();
        else
            return new ImListZipper<T>(first.tail().cons(newElement), second);
    }

    /**
     * The focus of the zipper.
     * 
     *     [1] [2, 3] getFocus()    =>  1
     *     [] [1, 2, 3] getFocus()  =>  throws ZipperHasNoFocusException
     *     
     * @throws NoSuchElementException if the first list is empty
     */
    public T getFocus()
    {
        if (first.isEmpty())
            throw new ZipperHasNoFocusException();
        else
            return first.head();
    }

    /**
     * The zipper that is the same as `this` but with `newElement` pushed onto the first list.
     * 
     *     [1] [2, 3] push(5)    =>  [1, 5] [2, 3]
     *     [] [1, 2, 3] push(5)  =>  [5] [1, 2, 3]
     * 
     * The new focus is `newElement`.
     */
    public ImListZipper<T> push(T newElement)
    {
        return new ImListZipper<T>(first.cons(newElement), second);
    }

    /**
     * The zipper that is `this` but with `elementsToInsert` pushed onto the first list.
     * 
     * The new focus is the last element of `elementsToInsert`.
     * 
     *     [1] [2, 3] push([5, 8, 13])  =>  [1, 5, 8, 13] [2, 3]
     *     [] [] push([5, 8, 13])       =>  [5, 8, 13] []
     * 
     * The order of elements in `elementsToInsert` is that specified by its iterator.
     */
    public ImListZipper<T> pushAll(Collection<T> elementsToInsert)
    {
        ImListZipper<T> insertAllAfter = this;

        for (T a : elementsToInsert)
        {
            insertAllAfter = insertAllAfter.push(a);
        }

        return insertAllAfter;
    }

    /**
     * The zipper that is `this` but with the last element popped from the first list.
     * 
     *     [1] [2, 3] pop()  =>  [1] [2, 3]
     *     [] [1] pop()      =>  throws ZipperHasNoFocusException
     * 
     * 
     * @throws ZipperHasNoFocusException if the first list is empty
     */
    public ImListZipper<T> pop()
    {
        if (first.isEmpty())
            throw new ZipperHasNoFocusException();
        else
            return new ImListZipper<T>(first.tail(), second);
    }

    /**
     * The index of the focus - the size of the first list.
     * 
     *     [1, 5, 8, 13] [2, 3] getIndex()  =>  4
     * 
     */
    public int getIndex()
    {
        return first.size();
    }

    /**
     * A string representation of this zipper.
     * 
     *     ImList.empty().getZipper().toString()  =>  "[] []"
     *     
     *     ImListZipper<Integer> z = ImList.onArray(1, 2, 3).getZipper();
     *     
     *     z.toString()                      =>  "[] [1, 2, 3]"
     *     z.next().toString()               =>  "[1] [2, 3]"
     *     z.next().next().toString()        =>  "[1, 2] [3]"
     *     z.next().next().next().toString() =>  "[1, 2, 3] []"
     * 
     */
    @Override
    public String toString()
    {
        return "" + getFirst() + " " + getSecond();
    }

    /**
     * A string representation of this zipper that uses the function `fn` on each element to get its string representation.
     * 
     * If this method was defined:
     * 
     *     public static String star(Object o)
     *     {
     *         return "*";
     *     }
     * 
     * then:
     *    
     *     Function1<String> starFn = FnFactory.on(this).getFnStatic(String.class, "star", Object.class);
     *     
     *     ImListZipper<String> z = ImList.onArray("Yabba", "dabba", "do").getZipper();
     *     
     *     z.next().toString(starFn)  =>  "[*] [*, *]"
     * 
     * @see immutablecollections.functions
     */
    public String toString(Function1<String> fn)
    {
        return getFirst().toString(fn) + " " + getSecond().toString(fn);
    }

    /**
     * The first list.
     * 
     *     [1, 5, 8, 13] [2, 3] getFirst()  =>  [1, 5, 8, 13]
     * 
     */
    public ImList<T> getFirst()
    {
        return first.reversed();
    }

    /**
     * The second list.
     * 
     *     [1, 5, 8, 13] [2, 3] getSecond()  =>  [2, 3]
     * 
     */
    public ImList<T> getSecond()
    {
        return second;
    }

    /**
     * `true` if there are more elements after the focus.
     * 
     *     [1] [2, 3] hasNext()  =>  true
     *     [] []      hasNext()  =>  false
     *     
     */
    public boolean hasNext()
    {
        return !second.isEmpty();
    }

    /**
     * `true` if there are more elements before the focus.
     * 
     *     [1, 2] [3] hasPrev()  =>  true
     *     [1] [2, 3] hasPrev()  =>  false
     *     [] [1]     hasPrev()  =>  false
     *     
     * Note that you can use {@link #prev()} even if `hasPrev()` is `false`.
     */
    public boolean hasPrev()
    {
        return first.size() > 1;
    }

    /**
     * A zipper iterator on `this`.
     */
    @Override
    public Iterator<ImListZipper<T>> iterator()
    {
        return new ImListZipperIterator<T>(this);
    }

}
